#include "BT.h"

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (NULL == node)
	{
		perror("malloc fail");
		exit(1);
	}
	node->data = x;
	node->left = node->right = NULL;
	return node;
}

BTNode* CreateBT()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	return node1;
}

void PrevOrder(BTNode* root)
{
	if (NULL == root)
	{
		printf("N ");
		return;
	}
	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

void InOrder(BTNode* root)
{
	if (NULL == root)
	{
		printf("N ");
		return;
	}
	InOrder(root->left);
	printf("%d ",root->data);
	InOrder(root->right);
}

void PostOrder(BTNode* root)
{
	if (NULL == root)
	{
		printf("N ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

int BTSize(BTNode* root)
{
	return NULL == root ? 0 : 1 + BTSize(root->left) + BTSize(root->right);  
}

int BTLeafSize(BTNode* root)
{
	if (NULL == root)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	else
	{
		return BTLeafSize(root->left) + BTLeafSize(root->right);
	}
}
  
int BTHeight(BTNode* root)
{
	if (NULL == root)
	{
		return 0;  
	}
	int leftheight = BTHeight(root->left);
	int rightheight = BTHeight(root->right);
	return 1 + (leftheight > rightheight ? leftheight : rightheight);
}

int BTLevelKSize(BTNode* root, int k)
{
	if (NULL == root)
	{
		return 0;
	}
	if (1 == k)
	{
		return 1;
	}
	return BTLevelKSize(root->left,k-1)+BTLevelKSize(root->right,k-1);
}

BTNode* BTFind(BTNode* root, BTDataType x)
{
	if (NULL == root)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* lefttree = BTFind(root->left,x);
	if (lefttree)
	{
		return lefttree;
	}
	BTNode* righttree = BTFind(root->right, x);
	if (righttree)
	{
		return righttree;
	}
	return NULL;
}

void BTDestroy(BTNode* root)
{
	if (NULL == root)
	{
		return;
	}
	BTDestroy(root->left);
	BTDestroy(root->right);
	free(root);
}

#include "Queue.h"

void BTLevelOrder(BTNode* root)
{
	if (NULL == root)
	{
		return;
	}
	Queue queue;
	QueueInit(&queue);
	QueuePush(&queue,root);
	while (!QueueEmpty(&queue))
	{
		BTNode* front = QueueFront(&queue);
		QueuePop(&queue);  
		printf("%d ", front->data);
		if (front->left)
		{
			QueuePush(&queue, front->left);
		}
		if (front->right)
		{
			QueuePush(&queue, front->right);
		}
	}
	QueueDestroy(&queue);
	printf("\n");
}

bool IsCompleteBT(BTNode* root)
{
	Queue queue;
	QueueInit(&queue);
	QueuePush(&queue,root);
	while (1)
	{
		BTNode* front = QueueFront(&queue);
		QueuePop(&queue);
		if (NULL == front)
		{
			break;
		}
		QueuePush(&queue, front->left);
		QueuePush(&queue, front->right);
	}
	bool ret = true;
	while (!QueueEmpty(&queue))
	{
		if (QueueFront(&queue))
		{
			ret = false;
			break;
		}
		QueuePop(&queue);
	}
	QueueDestroy(&queue);
	return ret;
}





     
